1. Field of the Invention
The present invention relates to fast Fourier transform, and, more particularly, to a method and system for fast Fourier transform that reduces the required amount of logic resources.
2. Description of the Related Art
Historically, fast Fourier transform (“FFT”) has been used to transform time domain data into frequency domain data and vice versa. FFT algorithms have a host of useful applications. For example, FFT can be used to convert sonar data detected in real-time into the frequency domain, where any dominant frequencies radiated by a sonar contact can be readily observed; this would be impossible looking at the time domain data alone. Frequency domain data is also useful for other sensor signal processing such as radar, as well as in the fields of communications, image processing, voice recognition, among many others.
The drawback to the use of FFT processing is that it can be very computationally expensive. Even though current FFT represents approximately a 100-to-1 reduction in required computation power compared to older discrete Fourier transform (“DFT”) algorithms, typical signal processing FFT applications typically require tens of millions of computations per second, thereby requiring a significant computational load. This computational load increases dramatically with large bit depth data streams, and in some cases can outstrip available logic resources.
As a result of the heavy drain on computation resources produced by the use of FFT, there have been many attempts to reduce the amount of required processor resources. Some of these efforts have been directed towards reducing the number of computations required in the underlying mathematical operations themselves. Other efforts have involved various ways of rearranging the computation resources so as to split the data and “cascade” the required computations, or other techniques. None of these prior art techniques, however, have solved the problem of effectively computing FFT for very large bit depth data.